\(\(\(\ \)\(The\ fastest\ Algorithm\ to\ calculate\ \ n\^\(n\^\(n\^\(n\^\(n⋰\^n\)\)\)\)\ \((mod\ 10)\)\ and\ \(\((mod\ 100)\)\(.\)\)\)\)\)

Kazuaki Fujii 
Satoshi Hashiba
Ryohei Miyadera

1.Introduction.  We are going to study the  number (n^((n^((n^((n^(n(⋰^n))))))))), where we use n n-times. This number can be expressed as n↑↑n by the Knuth's arrow notation.  This number has been studied by many people  See Eric W. Weisstein et al[1]. It is well known that the number (n^((n^((n^((n^(n(⋰^n))))))))) can be very big if n ≥ 4.  When n = 4, this number has approximately 8.072304726028225`*^153 digits.  As  n increases, this number becomes bigger and bigger and even the most powerful conmputers cannot calculate it correctly. Many people have tried to find a good algorithm to calculate (n^((n^((n^((n^(n(⋰^n)))))))))(mod m), where m is a arbitrary number.  You can find good algorithms in Ilan Vardi[4].  In this article we denote  p≡r  (mod q)  by  Mod[p,q]=Mod[r,q].  Note that we denote by Mod[p,q] the least nonnegative residue of the number p under modulus q.  
    We found a very interesting fact that \(Mod[n\^\(n\^\(n\^\(\^\(⋰\^\(n\^n\)\)\)\)\), 10]\) depends only on  Mod[n,20]and \(Mod[n\^\(n\^\(n\^\(\^\(⋰\^\(n\^n\)\)\)\)\), 
        100]\)depends only on Mod[n,100].  Therefore you can easily calculate \(Mod[
          n\^\(n\^\(n\^\(\^\(⋰\^\(n\^n\)\)\)\)\), 10]\)and \(Mod[
          n\^\(n\^\(n\^\(\^\(⋰\^\(n\^n\)\)\)\)\), 100]\) by calculating  Mod[n,20] and Mod[n,100] and reading Chart 1 and 2 in our article. This will make the fastest algorithm to calculate  \(Mod[
          n\^\(n\^\(n\^\(\^\(⋰\^\(n\^n\)\)\)\)\), 10]\)and  \(Mod[
          n\^\(n\^\(n\^\(\^\(⋰\^\(n\^n\)\)\)\)\), 100]\)in the world!
    As easily seen the result here can be generalized to the case of (10^(s ))instead of 10 and 100, but we study only the cases of 10 and 100 in this article because of their straightfowardness.

In the following lemmas  s  and  u are arbitrary nonnegative integers.

Lemma 1.  Let  λ be  the Carmichael function. The function has the following properties.
(1) (n^(λ(q)))=1 (mod q) for any positive integer  n relatively prime to q.
(2)  λ((5^s)×(2^u)) = 4×(5^(s - 1))  for any positive integer s  and integer u = 1,2,3.
(3)  λ(4)=2.
    These are famous properties of the Carmichael function, so we omit the proof.  See Eric W. Weisstein[2],[3].

Lemma 2. For any positive integer t relatively prime to 10 and for any positive number  m  Mod[(t^m),(5^s) (2^u)] = Mod[(t^Mod)[m, λ((5^s) (2^u))],(5^s) (2^u)].
Proof. By Lemma 1 we have Mod[(t^(λ((5^s) (2^u)))),(5^s) (2^u)] = 1, which concludes the proof.

Remark. By Lemma 2 we have Mod[(t^(m + u)),(5^s) (2^u)] = Mod[(t^(Mod[m, λ((5^s) (2^u))] + u)),(5^s) (2^u)].  We need this equation later in our article.

Lemma 3. For any positive integer k Mod[((((2^k)))^(m + u)),(5^s) (2^u)] = Mod[\(TraditionalForm\`\((2\^k)\)\^\(Mod[m, λ(\(5\^s\) 2\^u)] + u\)\),(5^s) (2^u)].
Proof.  By Lemma 1 we have Mod[((((2^k)))^(λ((5^s)))),(5^s)]=1.  Since λ((5^s) (2^u))is a multiple of λ((5^s)), we get Mod[((((2^k)))^(λ((5^s) (2^u)))),(5^s)]=1, and hence we have 
                    Mod[((((2^k)))^(λ((5^s) (2^u))))((((2^k)))^u),(5^s)]= Mod[((((2^k)))^u),(5^s)]....(1)
    Clearly we have Mod[((((2^k)))^(λ((5^s) (2^u))))((((2^k)))^u),(2^u)]= Mod[ ((((2^k)))^u),(2^u)]....(2)
Therefore by (1) and (2) we have Mod[((((2^k)))^(λ((5^s) (2^u))))((((2^k)))^u),(5^s) (2^u)]= Mod[((((2^k)))^u),(5^s) (2^u)], by which we have
Mod[((((2^k)))^(m + u)),(5^s) (2^u)] = Mod[\(TraditionalForm\`\((2\^k)\)\^\(Mod[m, λ(\(5\^s\) 2\^u)] + u\)\),(5^s) (2^u)].

Remark. The above  proof was suggested by Ask Dr.Math.dr.math@mathforum.org

Lemma 4. For any positive integer h  Mod[((((5^h)))^(m + s)),(5^s) (2^u)] = Mod[\(TraditionalForm\`\((5\^h)\)\^\(Mod[m, λ(\(5\^s\) 2\^u)] + s\)\),(5^s) (2^u)].
Proof.  By Lemma 1 we have Mod[((((5^h)))^(λ((2^u)))),(2^u)]=1.  Since λ((5^s) (2^u))is a multiple of λ((2^u)), we get Mod[((((5^h)))^(λ((5^s) (2^u)))),(2^u)]=1, and hence we have 
                    Mod[((((5^h)))^(λ((5^s) (2^u))))((((5^h)))^s),(2^u)]= Mod[((((5^h)))^s),(2^u)]....(1)
    Clearly we have Mod[((((5^h)))^(λ((5^s) (2^u))))((((5^h)))^s),(5^s)]= Mod[ ((((5^h)))^s),(5^s)]....(2)
Therefore by (1) and (2) we have Mod[((((5^h)))^(λ((5^s) (2^u))))((((5^h)))^s),(5^s) (2^u)]= Mod[((((5^h)))^s),(5^s) (2^u)], by which we have
Mod[((((5^h)))^(m + s)),(5^s) (2^u)] = Mod[\(TraditionalForm\`\((5\^h)\)\^\(Mod[m, λ(\(5\^s\) 2\^u)] + s\)\),(5^s) (2^u)].

Lemma 5. For any positive integer n relatively prime to 5 Mod[(n^(m + u)),(5^s) (2^u)] = Mod[(n^(Mod[m, λ((5^s) (2^u))] + u)),(5^s) (2^u)].
Proof.  Since n is relatively prime to 5, there exist a nonnegative number k and a positive number t such that t is relatively prime to 10 and  n=(2^k)×t.  By Lemma 3 and the remark of Lemma 2 we have  Mod[((((2^k)×t))^(m + u)),(5^s) (2^u)] = Mod[\(TraditionalForm\`\((2\^k×t)\)\^\(Mod[m, λ(\(5\^s\) 2\^u)] + u\)\),(5^s) (2^u)], which concludes the proof.

Lemma 6. For any positive integer p and q  Mod[p,q] ≥ v implies that 
Mod[p-v,q]=Mod[p,q]-v.
The proof is clear from the definition of Mod[].

Lemma 7. λ(100)= λ((5^2)×(2^2))=20, λ(20)=λ(5×(2^2))=4 and λ(4)=λ((2^2))=2.
This is a direct result of Lemma 1.

Lemma 8. For any positive integers n and m Mod[(n^m),q] = Mod[Mod[n, q]^m,q].

This is also a simple property of Mod[ , ].  We will omit the proof.

Theorem 1. For any positive integer n relatively prime to 10 we have 
\(Mod[
          n\^\(n\^\(n\^\(\^\(⋰\^\(n\^n\)\)\)\)\), 100]\)= Mod[Mod[n, 100]^Mod[Mod[n, 20]^Mod[n, 4], 20], 100].
Proof. First we assume that n ≥ 4, then by using Lemma 2 and 7 3-times we have Mod[\(n\^\(n\^\(n\^\(\^\(⋰\^\(n\^n\)\)\)\)\)\),100]= \(Mod[
        n\^Mod[n\^Mod[n\^Mod[n\^\(\^\(⋰\^\(\^n\)\)\), 2], 4], 20], 100]\).  Since n is odd, we have [\(Mod[n\^\(\^\(⋰\^\(\^n\)\)\), 2]\)=1.  Therefore by using Lemma 8 for q = 100 and 20 we can conclude the proof of this theorem.  If n=3, then by using Lemma 2 and 7 2-times we have
Mod[(n^((n^n))), 100]= Mod[(n^Mod)[(n^Mod)[n, 4], 20], 100].  By using Lemma 8 for q = 100 and 20 we can conclude the proof of this theorem.

Theorem 2. Let  n  be a positive even integer which is relatively prime to 5. Then 
(1) If n > 2, then we have
\(Mod[
          n\^\(n\^\(n\^\(\^\(⋰\^\(n\^n\)\)\)\)\), 100]\)= Mod[Mod[n, 100]^Mod[Mod[n, 20]^4, 20], 100].
(2) If n = 2 ,then Mod[(2^2), 100]= 4.
Proof. First we assume that n > 3.  By using by Lemma 5(for u = 2 and s = 2) and Lemma 7 we have \(Mod[
          n\^\(n\^\(n\^\(\^\(⋰\^\(n\^n\)\)\)\)\), 100]\)= \(Mod[
        n\^\(Mod[n\^\(n\^\(\^\(⋰\^\(n\^n\)\)\)\) - 2, 20] + 2\), 100]\).  Since n is even and relatively prime to 5, we have Mod[\(n\^\(n\^\(\^\(⋰\^\(n\^n\)\)\)\), 20\)]≥2. Therefore  by Lemma 6 \(Mod[n\^\(n\^\(\^\(⋰\^\(n\^n\)\)\)\) - 2, 20] + 
        2\)= \(Mod[n\^\(n\^\(\^\(⋰\^\(n\^n\)\)\)\), 20]\).  By using Lemma 5(for u = 2 and s = 5) we have \(Mod[n\^\(n\^\(\^\(⋰\^n\)\)\), 20]\)=\(Mod[n\^\(Mod[n\^\(\^\(⋰\^n\)\) - 2, 4] + 2\) + 2, 
        20]\). Since n is even, n ≥ 4 and \(n\^\(\^\(⋰\^\(n\^n\)\)\)\)can be divided by 4, and hence \(Mod[n\^\(\^\(⋰\^\(n\^n\)\)\) - 2, 4]\)+2 =4.  Therefore by usingLemma 8 for q = 100 and 20 we can conclude the proof of this theorem.

Theorem 3. (1) For any positive odd integer n which is a multiple of 5 we have 
\(Mod[
          n\^\(n\^\(n\^\(\^\(⋰\^\(n\^n\)\)\)\)\), 100]\)= 25.
(2) For any positive integer n which is a multiple of 10 we have \(Mod[
          n\^\(n\^\(n\^\(\^\(⋰\^\(n\^n\)\)\)\)\), 100]\)= 0.
The proof is obvious, so we omit it.

Theorem 4. \(Mod[
          n\^\(n\^\(n\^\(\^\(⋰\^\(n\^n\)\)\)\)\), 100]\)depends only on Mod[n,100].
The proof is clear from Theorem 1, 2 and 3.

By Theorem 1, 2 and 3  we can make a Mathematica function calculatemod[] to calculate Mod[\(n\^\(n\^\(n\^\(\^\(⋰\^\(n\^n\)\)\)\)\)\),100] for any n, and by Theorem 4 we know that we only have to calculate M[n,100] for n = 0,2,⋯,99.

calculatemod[n_] := 
      Which[GCD[n, 10] == 1, 
        Mod[Mod[n, 100]^Mod[Mod[n, 20]^Mod[n, 4], 20], 100], n == 2, 
        4, GCD[n, 5] == 1 && EvenQ[n], 
        Mod[Mod[n, 100]^Mod[Mod[n, 20]^4, 20], 100], 
        Mod[n, 5] == 0 && OddQ[n], 25, Mod[n, 10] == 0, 
        0]

Chart 1.  The chart for Mod[\(n\^\(n\^\(n\^\(\^\(⋰\^\(n\^n\)\)\)\)\)\),100].  With this chart you have the fastest algorithm to calculate Mod[\(n\^\(n\^\(n\^\(\^\(⋰\^\(n\^n\)\)\)\)\)\),100].

({{the values of  Mod[n, 
              100], \(the\ corresponding\ values\ of\ Mod[
              n\^\(n\^\(n\^\(\^\(⋰\^\(n\^n\)\)\)\)\), 
              100]\)}, {0, 1, 2, 3, 4, 5, 6, 7, 8, 9, 0, 1, 4, 87, 96, 25, 56, 43, 56, 
          89}, {10, 11, 12, 13, 14, 15, 16, 17, 18, 19, 0, 11, 16, 53, 36, 25, 
          16, 77, 76, 79}, {20, 21, 22, 23, 24, 25, 26, 27, 28, 29, 0, 21, 96, 47, 76, 25, 
          76, 83, 96, 69}, {30, 31, 32, 33, 34, 35, 36, 37, 38, 39, 0, 31, 76, 13, 16, 25, 
          36, 17, 16, 59}, {40, 42, 42, 43, 44, 45, 46, 47, 48, 49, 0, 41, 56, 7, 56, 25, 
          96, 23, 36, 49}, {50, 51, 52, 53, 54, 55, 56, 57, 58, 59, 0, 51, 36, 73, 96, 25, 
          56, 57, 56, 39}, {60, 61, 62, 63, 64, 65, 66, 67, 68, 69, 0, 61, 16, 67, 36, 25, 
          16, 63, 76, 29}, {70, 71, 72, 73, 74, 75, 76, 77, 78, 79, 0, 71, 96, 33, 76, 25, 
          76, 97, 96, 19}, {80, 81, 82, 83, 84, 85, 86, 87, 88, 89, 0, 81, 76, 27, 16, 25, 
          36, 3, 16, 9}, {90, 91, 92, 93, 94, 95, 96, 97, 98, 99, 0, 91, 56, 93, 56, 25, 
          96, 37, 36, 99}})

Remark. There seems to be some unknown structures in the Chart 1.  For example for Mod[n,100]= 9,19,29,39,49,59,69,79,89,99 we have Mod[\(n\^\(n\^\(n\^\(\^\(⋰\^\(n\^n\)\)\)\)\), 100\)]=89,79,69,59,49,39,29,19,9,99.

Chart 2. The chart for Mod[\(n\^\(n\^\(n\^\(\^\(⋰\^\(n\^n\)\)\)\)\)\),10].  From the above chart we can see that Mod[\(n\^\(n\^\(n\^\(\^\(⋰\^\(n\^n\)\)\)\)\), 10\)](the last digit of \(Mod[n\^\(n\^\(n\^\(\^\(⋰\^\(n\^n\)\)\)\)\), 
        100]\)) depends only on Mod[n,20].  From this fact we can make a chart of Mod[\(n\^\(n\^\(n\^\(\^\(⋰\^\(n\^n\)\)\)\)\), 10\)].

({{the values of  Mod[n, 
              20], \(the\ corresponding\ the\ values\ of\ Mod[
              n\^\(n\^\(n\^\(\^\(⋰\^\(n\^n\)\)\)\)\), 
              10]\)}, {0, 1, 2, 3, 4, 5, 6, 7, 8, 9, 10, 0,1,{({{4 (if n = 2)}, {6 (if n  >  2)}}),7,6,5,6,3,6,9}, {11, 12, 13, 14, 15, 16, 17, 18, 19, 0, 1, 6, 3, 6, 5, 6, 7, 6, 
          9}})

Theorem 5. \(Mod[
          n\^\(n\^\(n\^\(\^\(⋰\^\(n\^n\)\)\)\)\), 10]\)depends only on Mod[n,20].
The proof is clear from Chart 2.

References  
Eric W. Weisstein et al[1]. "Power Tower."From MathWorld.
Eric W.Weisstein[2]."Carmichael Function."  From MathWorld.
Eric W.Weisstein[3]. "Totient Function." From MathWorld.
Ilan Vardi[4], Computational Recreations in Mathematica
             Addison-Wesley (1991)